namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0108. 将有序数组转换为二叉搜索树")]
    public class No0108_SortedArrayToBST : AbsBaseTestItem
    {
        /*
        将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
        本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(SortedArrayToBST,
                new int[] { -10, -3, 0, 5, 9 },
                equalsMethod: (v1, v2) => v1.TestEqualsJSON(v2),
                new TreeNode(0)
                {
                    left = new TreeNode(-3)
                    {
                        left = new TreeNode(-10),
                    },
                    right = new TreeNode(9)
                    {
                        left = new TreeNode(5),
                    }
                });
        }

        public TreeNode SortedArrayToBST(int[] nums)
        {
            TreeNode funcHelp(int[] nums, int left, int right)
            {
                if (left > right)
                {
                    return null;
                }
                int mid = (left + right + 1) / 2;
                TreeNode node = new TreeNode(nums[mid]);
                node.left = funcHelp(nums, left, mid - 1);
                node.right = funcHelp(nums, mid + 1, right);
                return node;
            };
            return funcHelp(nums, 0, nums.Length - 1);
        }
    }
}
